package LinkList;

public class _11设计链表_单链表 {

    public static void main(String[] args) {
        MyLinkedList ll = new MyLinkedList();
        ll.addAtIndex(0,1);
        ll.addAtIndex(0,2);
        ll.addAtIndex(2,3);
        for (int i = 0; i < ll.size; i++) {
            System.out.println(ll.get(i));
        }
    }

    //搞清楚两点
    //第一点 虚拟头节点(又或者称哨兵，哑结点)：
    //通过创建这个虚拟头结点，可以遍历整个链表，并且这个虚拟头结点不会随着链表的增删改而变化。
    //实际上它最大的作用是好将头节点的删除情况变为通用情况,它是人为添加的，方便于代码设计编写的
    //虚拟头结点的next对应的结点才是真正意义上的头结点，它会发生变化
    //第二点 链表的构成：
    //首先链表是一个表，所以它是一个对象，程序在对链表进行操作时，操作的对象就是这个链表，本代码中 MyLinkList 就是这个链表对象
    //其次链表内存在许多结点，而每个结点也是一个个对象，所以结点是链表的内部类，也意味着结点的单独存在没有意义
    //所以到这4个属性就很清晰了，分别是链表的大小size、虚拟头结点head和结点的值val、下一个结点next
    static class MyLinkedList {
        int size;
        private ListNode head;


        public MyLinkedList() {
            this.size = 0;
            this.head = new ListNode(0);
        }

        public int get(int index) {
            if(index >= size){
                return -1;
            }

            ListNode cur = head;
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
            return cur.val;

        }

        public void addAtHead(int val) {
            addAtIndex(0,val);
        }

        public void addAtTail(int val) {
             addAtIndex(size,val);
        }

        public void addAtIndex(int index, int val) {
            if(index > size){
                return;
            }
            index = Math.max(index, 0);
            size++;

            ListNode pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }

            ListNode cur = new ListNode(val);
            cur.next = pred.next;
            pred.next = cur;

        }

        public void deleteAtIndex(int index) {
            if(index >= size || index < 0){
                return;
            }
            size--;

            ListNode pred = head;
            for (int i = 0; i < index; i++) {
                pred = pred.next;
            }
            pred.next = pred.next.next;

        }

        class ListNode{
            private int val;
            private ListNode next;

            ListNode(int val){
                this.val = val;
            }
        }
    }
}
